package com.ronz.huffman;


import java.io.ByteArrayInputStream;
import java.util.*;

/**
 * @Description 赫夫曼编码
 *              1. 首先统计出每个字符出现的次数(权值)
 *              2. 将字符以及对应的权值记录在节点中
 *              3. 创建赫夫曼树
 *              4. 进行赫夫曼编码
 *              5. 将二进制编码转换成十进制存储到 byte 数组中
 * @Author Ronz
 * @Date 2021/1/20 20:45
 * @Version 1.0
 */
public class No2_HuffManEncode {

    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        HashMap<Byte, Integer> map = new HashMap<>();
        getWeight(str, map);
        List<CharNode> nodes = getNodeList(map);
        CharNode huffManTree = getHuffManTree(nodes);
        Map<Byte, String> codeMap = getCode(huffManTree);

        List<Byte> zip = zip(str, codeMap);
        System.out.println(zip);
    }


    // 统计每个字符出现的次数
    public static void getWeight(String str, Map<Byte, Integer> map){
        byte[] bytes = str.getBytes();
        for (byte by : bytes){
            if (map.containsKey(by)){    // 如果已经记录过，就把权值 +1
                map.put(by, map.get(by)+1);
            }else{  // 如果没有记录过，就添加，将权值初始化为 1
                map.put(by, 1);
            }
        }
    }

    // 将每个字符出现次数以及字符记录到节点中然后存放到 list 中
    public static List<CharNode> getNodeList(Map<Byte, Integer> map){
        ArrayList<CharNode> nodes = new ArrayList<>();
        for (Byte by : map.keySet()){
            nodes.add(new CharNode(map.get(by), by));
        }
        return nodes;
    }

    // 生成哈夫曼树
    public static CharNode getHuffManTree(List<CharNode> nodes){
        while (nodes.size() > 1){
            Collections.sort(nodes);    // 给节点按权值升序排序
            CharNode left = nodes.get(0);
            CharNode right = nodes.get(1);
            CharNode node = new CharNode(left.weight + right.weight, null); // 两个节点组成一个父节点
            node.left = left;   // 建立父子关系
            node.right = right;
            nodes.remove(left); // 从 list 中删除原节点
            nodes.remove(right);
            nodes.add(node);    // 添加新组成的节点
        }
        return nodes.get(0);
    }

    // 根据哈夫曼树生成二进制编码表
    public static void getBinaryCode(CharNode node, Map<Byte, String> map, int code, StringBuilder stringBuilder){
        StringBuilder builder = new StringBuilder(stringBuilder);   // 每递归一次，就把上次的编码记录下来，用于本次拼接
        if (node != null){
            builder.append(code);
            if (node.data == null){ // 如果是非叶子节点，继续递归
                getBinaryCode(node.left, map, 0, builder);    // 向左递归
                getBinaryCode(node.right, map, 1, builder);   // 向右递归
            }else{
                map.put(node.data, builder.toString());
            }
        }
    }

    // 生成二进制编码表
    public static Map<Byte, String> getCode(CharNode node){
        if (node == null){
            return null;
        }
        Map<Byte, String> map = new HashMap<>();
        StringBuilder builder = new StringBuilder();
        getBinaryCode(node.left, map, 0, builder);   // 左递归
        getBinaryCode(node.right, map, 1, builder);   // 右递归
        return map;
    }

    // 将二进制编码转换为十进制编码
    public static List<Byte> zip(String str, Map<Byte, String> map){
        String codeStr = "";
        byte[] bytes = str.getBytes();
        ArrayList<Byte> list = new ArrayList<>();
        for (byte b : bytes){
            codeStr += map.get(b);
        }

        for (int i=0; i<codeStr.length(); i+=8){
            if (i+8<codeStr.length()){
                list.add((byte)Integer.parseInt(codeStr.substring(i, i+8),2));
            }else{
                list.add(((byte) Integer.parseInt(codeStr.substring(i),2)));
            }
        }
        return list;
    }
}


/**
 * 节点：存放字符的权值和字符
 */
class CharNode implements Comparable<CharNode>{
    int weight; // 权值（次数）
    Byte data;  // 字符
    CharNode left;
    CharNode right;

    public CharNode(int weight, Byte data){
        this.weight = weight;
        this.data = data;
    }

    @Override
    public String toString() {
        return "CharNode{" +
                "weight=" + weight +
                ", data=" + data +
                '}';
    }

    @Override
    public int compareTo(CharNode o) {
        return this.weight - o.weight;
    }
}
